package com.leetcode.algorithm.common;

/**
 * Quick Find 的「并查集」实现代码
 * 
 * @author jie.deng
 *
 */
public class UnionFind01 {
	int roots[];

	public UnionFind01(int size) {
		roots = new int[size];
		for (int i = 0; i < size; i++) {
			roots[i] = i;
		}
	}

	private int findRoot(int x) {
		return roots[x];
	}

	public void union(int x, int y) {
		int rootX = findRoot(x);
		int rootY = findRoot(y);
		if (rootX != rootY) {
			for (int i = 0; i < roots.length; i++) {
				if (roots[i] == rootY) {
					roots[i] = rootX;
				}
			}
		}
	};

	public boolean isConnected(int x, int y) {
		return findRoot(x) == findRoot(y);
	}
}
